/**
 * Exercise 9.58
 * -----------------------------------------------------------------------------
 * Using the conventions of Exercise 9.1] give the sequence of binomial queues produced when the operations
    ```txt
    P R I O * R * * I * T * Y * * * Q U E * * * U * E
    ```
 * are performed on an initially empty binomial queue.
 * -----------------------------------------------------------------------------
 */
#include <assert.h>
#include <stdlib.h>

typedef char Item;
typedef struct PQnode* PQlink;
typedef struct pq* PQ;

struct PQnode {
    Item key;
    PQlink l;
    PQlink r;
};

struct pq {
    PQlink *bq;
};

#define maxBQsize 4
#define test(C, B, A) 4*(C) + 2*(B) + 1*(A)

static PQlink z = NULL;

/////////////////////////////////接口操作////////////////////////////////////
PQ PQinit();
PQlink PQinsert(PQ pq, Item v);
Item PQdelmax(PQ pq);

///////////////////////////////////辅助函数/////////////////////////////////
PQlink pair(PQlink p, PQlink q);
void BQjoin(PQlink *a, PQlink *b);

//////////////////////////////////测试用例/////////////////////////////////
void test_insert();

int main(int argc, char *argv[]) {
    test_insert();
    return 0;
}


PQlink pair(PQlink p, PQlink q) {
    if (p->key < q->key) {
        p->r = q->l;
        q->l = p;
        return q;
    }else {
        q->r = p->l;
        p->l = q;
        return p;
    }
}

void BQjoin(PQlink *a, PQlink *b) {
    int i;
    PQlink c = z;
    for (i = 0; i < maxBQsize; i++) {
        switch (test(c != z, b[i] != z, a[i] != z)) {
            case 2:
                a[i] = b[i];
                break;
            case 3:
                c = pair(a[i], b[i]);
                a[i] = z;
                break;
            case 4:
                a[i] = c;
                c = z;
                break;
            case 5:
                c = pair(c, a[i]);
                a[i] = z;
                break;
            case 6:
            case 7:
                c = pair(c, b[i]);
                break;
            default:
                break;
        }
    }
}



PQ PQinit() {
    PQ pq = (PQ)malloc(sizeof(*pq));
    pq->bq = (PQlink *)malloc(maxBQsize * sizeof(PQlink));

    int i;
    for (i = 0; i < maxBQsize; i++) {
        pq->bq[i] = z;
    }

    return pq;
}

PQlink PQinsert(PQ pq, Item v) {
    PQlink t = malloc(sizeof(*t));
    PQlink c = t;
    c->key = v;
    c->l = z;
    c->r = z;
    int i;

    for (i = 0; i < maxBQsize; i++) {
        if (c == z) {
            break;
        }
        if (pq->bq[i] == z) {
            pq->bq[i] = c;
            break;
        }
        c = pair(c, pq->bq[i]);
        pq->bq[i] = z;

    }

    return t;
}

Item PQdelmax(PQ pq) {
    int i;
    int max;
    PQlink x;
    Item v;
    PQlink temp[maxBQsize];

    for (i = 0, max = -1; i < maxBQsize; i++) {
        if (pq->bq[i] != z) {
            if ((max == -1) || (v < pq->bq[i]->key)) {
                max = i;
                v = pq->bq[max]->key;
            }
        }
    }

    x = pq->bq[max]->l;
    for (i = max; i < maxBQsize; i++) {
        temp[i] = z;
    }
    for (i = max; i > 0; i--) {
        temp[i-1] = x;
        x = x->r;
        temp[i-1]->r = z;
    }

    free(pq->bq[max]);
    pq->bq[max] = z;

    BQjoin(pq->bq, temp);
    return v;
}

void test_insert() {
    PQ pq = PQinit();
    // P-R-I-O-*-R-*-*-I-*-T-*-Y-*-*-*-Q-U-E-*-*-*-U-*-E
    PQinsert(pq, 'P');
    PQinsert(pq, 'R');
    PQinsert(pq, 'I');
    PQinsert(pq, 'O');
    assert(pq->bq[0] == z);
    assert(pq->bq[1] == z);
    assert(pq->bq[2]->key == 'R');
    assert(pq->bq[2]->r == z);
    assert(pq->bq[2]->l->key == 'O');
    assert(pq->bq[2]->l->l->key == 'I');
    assert(pq->bq[2]->l->r->key == 'P');

    assert(PQdelmax(pq) == 'R');
    PQinsert(pq, 'R');
    assert(PQdelmax(pq) == 'R');
    assert(PQdelmax(pq) == 'P');
    assert(pq->bq[0] == z);
    assert(pq->bq[1]->key == 'O');
    assert(pq->bq[1]->r == z);
    assert(pq->bq[1]->l->key == 'I');
    PQinsert(pq, 'I');
    assert(PQdelmax(pq) == 'O');
    assert(pq->bq[0] == z);
    assert(pq->bq[1]->key == 'I');
    assert(pq->bq[1]->r == z);
    assert(pq->bq[1]->l->key == 'I');
    PQinsert(pq, 'T');
    assert(PQdelmax(pq) == 'T');
    assert(pq->bq[0] == z);
    assert(pq->bq[1]->key == 'I');
    assert(pq->bq[1]->r == z);
    assert(pq->bq[1]->l->key == 'I');
    PQinsert(pq, 'Y');
    assert(PQdelmax(pq) == 'Y');
    assert(PQdelmax(pq) == 'I');
    assert(PQdelmax(pq) == 'I');
    assert(pq->bq[0] == z);
    assert(pq->bq[1] == z);
    assert(pq->bq[2] == z);
    assert(pq->bq[3] == z);
    PQinsert(pq, 'Q');
    PQinsert(pq, 'U');
    PQinsert(pq, 'E');
    assert(PQdelmax(pq) == 'U');
    assert(PQdelmax(pq) == 'Q');
    assert(PQdelmax(pq) == 'E');
    assert(pq->bq[0] == z);
    assert(pq->bq[1] == z);
    assert(pq->bq[2] == z);
    assert(pq->bq[3] == z);
    PQinsert(pq, 'E');
    assert(pq->bq[0]->key == 'E');






    // PQinsert(pq, 'Q');
    // PQinsert(pq, 'U');
    // PQinsert(pq, 'E');
    // PQinsert(pq, 'S');
    // PQinsert(pq, 'T');
    // PQinsert(pq, 'I');
    // PQinsert(pq, 'O');
    // PQinsert(pq, 'N');
}